package OthersQuestions.q01_bitDanceInterview;

/*
朴素回溯
 */
public class Solution_4 {
    int k, num = 0, max = 0; // 假定给定的k为正数，无法组成比k小的数时返回0
    int[] nums;
    public int largestLessThanK(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        backtrack();
        return max;
    }
    private void backtrack() {
        for(int i = 0; i < nums.length; i++) {
            num = num * 10 + nums[i];
            if(num > k) { // 剪枝，跳到同层下一个元素
                num = (num - nums[i]) / 10;
                continue; // 注意是continue不是return
            }
            max = Math.max(max, num);
            backtrack();
            num = (num - nums[i]) / 10; // 撤销
        }
    }

}
